class Solution {
    public double myPow(double x, int n) {
        if (x == 0 && n < 0) {
            throw new RuntimeException("invalid parameters");
        }
        long b = n;
        if (n < 0) {
            return (1.0 / pow3(x, -b));
        }
        return pow3(x, b);
    }

    // 递归也会超时
    private double pow2(double base, int n) {
        if (n == 0) {
            return 1;
        }
        if (n == 1) {
            return base;
        }
        double res = pow2(base, n >> 1);
        res *= res;
        if ((n & 1) == 1) {
            res *= base;
        }
        return res;
    }

    // 使用遍历的话会超时
    private double pow1(double base, int n) {
        double res = 1;
        for (int i = 1; i <= n; i++) {
            res *= base;
        }
        return res;
    }

    // 快速幂
    private double pow3(double base, long n) {
        if (n == 0) {
            return 1;
        }
        double res = 1.0;
        while (n > 0) {
            if ((n & 1) == 1) res *= base;
            base *= base;
            n >>= 1;
        }
        return res;
    }


    public static void main(String[] args) {
        Solution s = new Solution();
        double ans = s.myPow(2.00000, -2147483648);
        System.out.println(ans);

        test();
    }

    public static void test() {
        System.out.println(2147483648L);
        System.out.println((int) 2147483648L);
        System.out.println(Integer.MAX_VALUE);

        int a = -2147483648;
        System.out.println(a);
        System.out.println(-a);
    }
}